package com.veal98.bactrack;

import java.util.ArrayList;
import java.util.List;

public class LC131 {

    private List<List<String>> res = new ArrayList<>();

    public List<List<String>> partition(String s) {
        if (s == null || s.length() == 0) {
            return res;
        }

        List<String> track = new ArrayList<>();
        // 标志位，从哪个位置开始切割
        int start = 0;
        backtrack(s, start, track);
        return res;
    }

    private void backtrack(String s, int start, List<String> track) {
        if (start == s.length()) {
            res.add(new ArrayList<>(track));
            return;
        }

        // 遍历选择列表
        for (int i = start; i < s.length(); i ++) {
            // 1. 剪枝(不是回文串)
            if(!isPalindrome(s, start, i)) {
                continue;
            } else {
                // 2. 做选择, 获取回文子串 s[start,i]
                // substing 左闭右开
                track.add(s.substring(start, i + 1));
            }

            // 3. 进入下一层解空间树
            backtrack(s, i + 1, track);
            // 4. 回溯
            track.remove(track.size() - 1);
        }
    }

    // 判断 s[start, end] 是否回文
    private boolean isPalindrome(String s, int start, int end) {
        int left = start;
        int right = end;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                // 不是回文串
                return false;
            }
            left ++;
            right --;
        }
        return true;
    }


}
